from math import inf

inf = float('inf')

class Solution(object):
    def minTaps(self, n, ranges):
        """
        方法：贪心算法
        
        逻辑:
            1. 计算每个起始位置能到达的最远距离
            2. 在当前位置能到达的范围内，不断寻找并更新最远可达位置
            3. 当无法继续前进时返回-1，否则累加所需水龙头数量
        
        Args:
            n: int, 花园长度
            ranges: List[int], 每个位置水龙头的喷水范围
        
        Returns:
            int: 最少需要的水龙头数量，无法覆盖则返回-1
        
        Time: O(n), 其中n为花园长度
        
        Space: O(n), 需要存储最远可达距离数组
        """
        rightMost = list(range(n + 1))
        for i, r in enumerate(ranges):
            start = max(0, i - r)
            end = min(n, i+r)
            rightMost[start] = max(rightMost[start], end)
        last = ret = pre = 0
        for i in range(n):
            last = max(last, rightMost[i])
            if i == last:
                return -1
            if i == pre:
                pre = last
                ret += 1
        return ret

    def minTaps1(self, n, ranges):
        """
        方法：动态规划
        
        逻辑:
            1. 将每个水龙头的覆盖范围转换为区间
            2. 对区间按起点排序
            3. 使用dp数组记录覆盖到每个位置所需的最少水龙头数
        
        Args:
            n: int, 花园长度
            ranges: List[int], 每个位置水龙头的喷水范围
        
        Returns:
            int: 最少需要的水龙头数量，无法覆盖则返回-1
        
        Time: O(n * R), 其中n为花园长度，R为最大喷水范围
        
        Space: O(n), 需要dp数组存储中间结果
        """
        intervals = []
        for i, r in enumerate(ranges):
            start = max(0, i-r)
            end = min(n, i + r)
            intervals.append((start, end))
        intervals.sort()

        dp = [inf] * (n + 1)
        dp[0] = 0
        for start, end in intervals:
            if dp[start] == inf:
                return -1
            for j in range(start, end + 1):
                dp[j] = min(dp[j], dp[start] + 1)
        return dp[n]

            